package com.lun.swordtowardoffer2.c04;

public class FlattenList {
	
	public void flatten(Node head) {
		while(head != null) {
			Node next = head.next;
			if(head.child != null) {
				flattenNode(head);
			}
			head = next;
		}
	}
	
	private void flattenNode(Node head) {
		Node childHeadPrev = head;
		Node childHead = head.child;
		
		Node childTail = childHead, p = childHead;
		Node childTailNext = head.next;
		
		childHeadPrev.next = childHead;
		childHead.prev = childHeadPrev;
		childHeadPrev.child = null;
		
		while(p != null) {
			if(p.child != null)
				flattenNode(p);
			
			if(p.next == null)
				childTail = p;
				
			p = p.next;
		}
		
		childTail.next = childTailNext;
		if(childTailNext != null)
			childTailNext.prev = childTail;
	}
	
	
	public static class Node{
		public int val;
		public Node prev;
		public Node next;
		public Node child;
		
		public Node(int val) {
			this.val = val;
		}
		
		public static Node of(int... nums) {
			if(nums == null)
				return null;
			
			Node head = new Node(nums[0]);
			Node tail = head;
			
			for(int i = 1; i < nums.length; i++) {
				tail.next = new Node(nums[i]);
				tail.next.prev = tail;
				tail = tail.next;
			}
			
			return head;
		}
		
		public static boolean equals(Node head1, Node head2) {
			return equals(head1, head2, true);
		}
		
		private static boolean equals(Node head1, Node head2, boolean forwardFlag) {
			
			if(head1 == null ^ head2 == null) return false;
			
			if(head1 != null && head2 != null) {
				if(head1.val != head2.val)
					return false;
				
				if(head1.next == null && head2.next == null)
					forwardFlag = false;
				
				if(forwardFlag) {
					return equals(head1.next, head2.next, forwardFlag);
				}else {
					return equals(head1.prev, head2.prev, forwardFlag);
				}
			}
			
			return true;
		}
	}
}
